package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         658,
		Discription: "在有序数组中找k个和x最接近的数",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
			"双指针": 1,
		},
	})
}

//用sort.Find找到值为x的最小索引 or 插入x的最小索引位置
//i=index-1 j=index开双指针找k个
func FindClosestElements(arr []int, k int, x int) []int {
	delta := func(index int) int {
		res := arr[index] - x
		if res >= 0 {
			return res
		}

		return -res
	}

	index, _ := sort.Find(len(arr), func(i int) int {
		//>0表示x在i右边，<0表示x在i左边
		return x - arr[i]
	})

	if index == len(arr) {
		index--
	}

	i := index - 1
	j := index
	count := 0
	for count < k && (i >= 0 || j < len(arr)) {
		if i < 0 {
			j++
			count++
			continue
		}

		if j >= len(arr) {
			i--
			count++
			continue
		}

		if delta(i) <= delta(j) {
			i--
		} else {
			j++
		}
		count++
	}

	return arr[i+1 : j]
}